package com.south.base.test.arithmetic.link;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 单链表处理
 *
 * @author Administrator
 * @date 2020/5/27 11:12
 */
public class SingleLink {
    /**
     * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        ListNode start = head;
        ListNode endK = head;
        for (int i = 0; i < k; i++) {
            endK = endK.next == null ? head : endK.next;
        }
        while (endK.next != null) {
            endK = endK.next;
            start = start.next;
        }
        endK.next = head;
        ListNode res = start.next;
        start.next = null;
        return res;
    }

    public ListNode rotateRight2(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        int length = 1;
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
            length++;
        }
        //已经把链表首尾相接的连上了
        cur.next = head;
        //这个是算法的关键，找到应该在何处断开
        int m = length - k % length;
        for (int i = 0; i < m; i++) {
            cur = cur.next;
        }
        //获得新的链表头节点
        ListNode newHead = cur.next;
        //断开链表环
        cur.next = null;
        return newHead;
    }

    /**
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     * k 是一个正整数，它的值小于或等于链表的长度。
     * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode prevNode = dummy;

        while ((head != null) && (head.next != null)) {

            ListNode secondNode = head;

            ListNode nextNodeK = prevNode;
            for (int i = 0; i < k; i++) {
                if (nextNodeK.next == null) {
                    return dummy.next;
                }
                nextNodeK = nextNodeK.next;
            }
            for (int i = 1; i < k; i++) {
                ListNode a = secondNode.next;
                ListNode b = a.next;
                a.next = prevNode.next;
                prevNode.next = a;
                secondNode.next = b;
            }

            prevNode = secondNode;
            head = secondNode.next; // jump
        }

        return dummy.next;
    }

    /**
     * 翻转链表
     */
    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    /**
     * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
     * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     */
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode prevNode = dummy;

        while ((head != null) && (head.next != null)) {

            ListNode firstNode = head;
            ListNode secondNode = head.next;

            prevNode.next = secondNode;
            firstNode.next = secondNode.next;
            secondNode.next = firstNode;

            prevNode = firstNode;
            head = firstNode.next; // jump
        }

        return dummy.next;
    }

    /**
     * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode listNode = null, result = null;
        int pre = 0;
        do {
            ListNode listNodeTemp = null;
            if (l1 != null && l2 != null) {
                int sum = l1.val + l2.val + pre;
                if (sum >= 10) {
                    listNodeTemp = new ListNode(sum - 10);
                    pre = 1;
                } else {
                    listNodeTemp = new ListNode(sum);
                    pre = 0;
                }
                l1 = l1.next;
                l2 = l2.next;
            } else if (l1 != null) {
                int sum = l1.val + pre;
                if (sum >= 10) {
                    listNodeTemp = new ListNode(sum - 10);
                    pre = 1;
                } else {
                    listNodeTemp = new ListNode(sum);
                    pre = 0;
                }
                l1 = l1.next;
            } else if (l2 != null) {
                int sum = l2.val + pre;
                if (sum >= 10) {
                    listNodeTemp = new ListNode(sum - 10);
                    pre = 1;
                } else {
                    listNodeTemp = new ListNode(sum);
                    pre = 0;
                }
                l2 = l2.next;
            }
            if (listNode != null) {
                listNode.next = listNodeTemp;
                listNode = listNode.next;
            } else {
                result = listNode = listNodeTemp;
            }
        } while (l1 != null || l2 != null);
        if (pre == 1) {
            listNode.next = new ListNode(pre);
        }
        return result;
    }

    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }

    /**
     * 合并两个有序链表
     *
     * @param l1
     * @param l2
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode resultNode = new ListNode(0);
        mergeTwoLists(l1, l2, resultNode);
        return resultNode.next;
    }

    public void mergeTwoLists(ListNode l1, ListNode l2, ListNode resultNode) {
        if (l1 == null && l2 == null) {
        } else if (l1 == null) {
            resultNode.next = new ListNode(l2.val);
            mergeTwoLists(null, l2.next, resultNode.next);
        } else if (l2 == null) {
            resultNode.next = new ListNode(l1.val);
            mergeTwoLists(l1.next, null, resultNode.next);
        } else if (l1.val > l2.val) {
            resultNode.next = new ListNode(l2.val);
            mergeTwoLists(l1, l2.next, resultNode.next);
        } else {
            resultNode.next = new ListNode(l1.val);
            mergeTwoLists(l1.next, l2, resultNode.next);
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return mergeKLists(lists, 0, lists.length - 1);
    }

    /**
     * 二分
     *
     * @param lists
     * @param start
     * @param end
     * @return
     */
    private ListNode mergeKLists(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        ListNode l1, l2;
        if (end - start > 1) {
            l1 = mergeKLists(lists, start, (start + end) / 2);
            l2 = mergeKLists(lists, (start + end) / 2 + 1, end);
        } else {
            l1 = lists[start];
            l2 = lists[end];
        }
        return merge2Lists(l1, l2);
    }

    private ListNode merge2Lists(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        ListNode l = res;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                l.next = l1;
                l1 = l1.next;
                l = l.next;
            } else {
                l.next = l2;
                l2 = l2.next;
                l = l.next;
            }
        }
        if (l1 != null) {
            l.next = l1;
        }
        if (l2 != null) {
            l.next = l2;
        }

        return res.next;
    }

    /**
     * 堆
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists4(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        //创建一个小根堆，并定义好排序函数
        PriorityQueue<ListNode> queue = new PriorityQueue((Comparator<ListNode>) (o1, o2) -> (o1.val - o2.val));
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        //这里跟上一版不一样，不再是一股脑全部放到堆中
        //而是只把k个链表的第一个节点放入到堆中
        for (int i = 0; i < lists.length; i++) {
            ListNode head = lists[i];
            if (head != null) {
                queue.add(head);
            }
        }
        //之后不断从堆中取出节点，如果这个节点还有下一个节点，
        //就将下个节点也放入堆中
        while (queue.size() > 0) {
            ListNode node = queue.poll();
            cur.next = node;
            cur = cur.next;
            if (node.next != null) {
                queue.add(node.next);
            }
        }
        cur.next = null;
        return dummy.next;
    }

    /**
     * 插入
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        ListNode resultNode = new ListNode(Integer.MIN_VALUE);
        ListNode tmp = resultNode;
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] == null) {
                continue;
            }
            if (tmp.next == null) {
                resultNode.next = lists[i];
                tmp.next = lists[i];
                continue;
            }
            while (tmp.next != null && lists[i] != null) {
                if (lists[i].val >= tmp.val && lists[i].val <= tmp.next.val) {
                    ListNode t = tmp.next;
                    tmp.next = new ListNode(lists[i].val);
                    tmp.next.next = t;
                    lists[i] = lists[i].next;
                } else if (lists[i].val > tmp.next.val) {
                    tmp = tmp.next;
                }
            }
            if (tmp.next == null) {
                tmp.next = lists[i];
            }
            tmp = resultNode;
        }
        return resultNode.next;
    }

    public ListNode mergeKLists3(ListNode[] lists) {
        ListNode resultNode = new ListNode(0);
        int minIndex = -1;
        ListNode tmp = resultNode;
        while (true) {
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] == null) {
                    continue;
                }
                if (minIndex < 0 || lists[minIndex].val >= lists[i].val) {
                    minIndex = i;
                }
            }
            if (minIndex >= 0) {
                tmp.next = new ListNode(lists[minIndex].val);
                lists[minIndex] = lists[minIndex].next;
                tmp = tmp.next;
                minIndex = -1;
            } else {
                break;
            }
        }
        return resultNode.next;
    }

    /**
     * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        // 将first指针后移n位
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }
        // 当first指针到达最后时结束循环，此时second指针指向的位置next为应删除位置
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

    /**
     * 移除链表元素
     * 删除链表中等于给定值 val 的所有节点。
     */
    public ListNode removeElements(ListNode head, int val) {
        ListNode res = new ListNode(0);
        res.next = head;
        ListNode pre = res;
        while (head != null) {
            if (head.val == val) {
                pre.next = head.next;
                head = head.next;
                continue;
            }
            head = head.next;
            pre = pre.next;
        }
        return res.next;
    }

    /**
     * 链表的中间结点
     * 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
     * 如果有两个中间结点，则返回第二个中间结点。
     * 给定链表的结点数介于 1 和 100 之间。
     * 数组
     */
    public ListNode middleNode(ListNode head) {
        ListNode[] A = new ListNode[100];
        int t = 0;
        while (head != null) {
            A[t++] = head;
            head = head.next;
        }
        return A[t / 2];
    }

    /**
     * 快慢指针法
     */
    public ListNode middleNode2(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    /**
     * 删除排序链表中的重复元素
     * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = head;
        ListNode res = head;
        head = head.next;
        while (head != null) {
            if (pre.val == head.val) {
                pre.next = head.next;
                head = head.next;
            } else {
                pre = pre.next;
                head = head.next;
            }
        }
        return res;
    }

    /**
     * 删除排序链表中的重复元素 II
     * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
     */
    public ListNode deleteDuplicates2(ListNode head) {
        if (head == null) {
            return null;
        }
        int val = head.val - 1;
        ListNode pre = new ListNode(val);
        pre.next = new ListNode(val);
        pre.next.next = head;
        ListNode res = pre;
        ListNode same = null;
        while (head != null) {
            if (head.val == val) {
                pre.next.next = head = head.next;
                same = pre.next;
                continue;
            }
            if (pre.next == same) {
                val = head.val;
                pre.next = pre.next.next;
                head = head.next;
                continue;
            }
            val = head.val;
            pre = pre.next;
            head = head.next;
        }
        if (pre.next == same) {
            pre.next = pre.next.next;
        }
        return res.next.next;
    }

    /**
     * 相交链表，找到两个单链表相交的起始节点。
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tmpA = headA, tmpB = headB;
        boolean fa = true, fb = true;
        while (tmpA != null && tmpB != null) {
            if (tmpA == tmpB) {
                return tmpA;
            }
            tmpA = tmpA.next;
            tmpB = tmpB.next;
            if (tmpA == null && fa) {
                fa = false;
                tmpA = headB;
            }
            if (tmpB == null && fb) {
                fb = false;
                tmpB = headA;
            }
        }
        return null;
    }

    public ListNode toNode(String string) {
        String[] strings = string.split(",");
        ListNode res = new ListNode(Integer.valueOf(strings[0]));
        ListNode tmp = res;
        for (int i = 1; i < strings.length; i++) {
            tmp.next = new ListNode(Integer.valueOf(strings[i]));
            tmp = tmp.next;
        }
        return res;
    }
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
